A graphics accelerator is a specialized graphics processing subsystem for a computer system that relieves a host processor from performing all the graphics processing involved in rendering a graphics image on a display device. The host processor of the computer system executes an application program that generates geometry information used to define graphics elements on the display device. The graphics elements that are displayed are typically modeled from polygon graphics primitives. For example, a triangle is a commonly used polygon for rendering three dimensional objects on the display device. Setup calculations are initially performed by the host processor to define the triangle primitives. The application program then transfers the geometry information from the processor to the graphics processing system so that the triangles may be modified by adding shading, hazing, or other features before being displayed. The graphics processing system, as opposed to the processor, has the task of rendering the corresponding graphics elements on the display device to allow the processor to handle other system requests.
Some polygon graphics primitives also include specifications to map texture data, representative of graphic images, within the polygons. Texture mapping refers to techniques for adding surface detail, or a texture map, to areas or surfaces of the polygons displayed on the display device. A typical texture map includes point elements (“texels”) which reside in a (s, t) texture coordinate space. The graphics data representing the texels of a texture map are stored in a memory of the computer system and used to generate the color values of point elements (“pixels”) of the display device which reside in an (x, y) display coordinate space. Where the original graphics primitives are three dimensional, texture mapping often involves maintaining certain perspective attributes with respect to the surface detail added to the graphics primitive, a texture image is represented in the computer memory as a bitmap or other raster-based encoded format.
Generally, the process of texture mapping occurs by accessing the texels from the memory that stores the texture data, and transferring the texture map texels to predetermined points of the graphics primitive being texture mapped. The (s, t) coordinates for the individual texels are calculated and then converted to memory addresses. The texture map data are read out of memory and applied within the respective polygon in particular fashions depending on the placement and perspective of their associated polygon. The process of texture mapping operates by applying color or visual attributes of texels of the (s, t) texture map to corresponding pixels of the graphics primitive on the display. Thus, color values for pixels in (x, y) display coordinate space are determined based on sampled texture map values. After texture mapping, a version of the texture image is visible on surfaces of the graphics primitive, with the proper perspective, if any.
The process of texture mapping requires a great demand on the memory capacity of the computer graphics processing system because a lot of texture maps are accessed from memory during a typical display screen update cycle. Since the frequency of the screen update cycles is rapid, the individual polygons of the screen (and related texture map data per polygon) need to be accessed and updated at an extremely rapid frequency requiring great data throughput capacities. In view of the above memory demands, high performance graphics hardware units often integrate a graphics processor and a low access time cache memory unit onto a common substrate for storing and retrieving blocks of texture data at high speeds.
A tag cache, typically implemented by using a random access memory (RAM), stores a “tag” for each data block stored in a data cache. The tag is usually the memory address, or a portion thereof, corresponding the location in the host memory where the data is stored. In a fully associative cache, that is, a cache where data may be stored in any of the data storage locations of the data cache, the address of the requested data must be compared with each of the tags stored in the tag cache. With texture caches, as a texture-mapped polygon is processed a cache controller must check each address present in the tag cache to determine whether a requested block of texture data is stored in the texture cache. If the requested texture data is present in the data cache, it is immediately provided for texture application to the polygon. However, if the requested memory address is not present in the texture cache, the cache controller unit must first obtain the desired block of texture data from memory. The data and tag caches are updated with the retrieved data and corresponding memory address, respectively, prior to being provided for texture application.
Although cache memory units improve the speed at which data may be provided for processing, implementing a cache memory unit with a tag RAM often requires complex circuitry to examine all of the addresses of the texture data present in the texture cache. This is especially the case for a fully associative cache. The complexity of the circuitry results in increased access times and may require a substantial portion of the substrate for their layout. Therefore, it can be appreciated that there is a need for a texture cache having reduced complexity and that can provide texture mapped data at high speeds.